package com.yangli.leecode.b;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ly
 * @description https://leetcode-cn.com/problems/3sum/
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * @data 2022/4/25
 */
public class ThreeSum {
    public static void main(String[] args) {
        ThreeSum threeSum = new ThreeSum();
        System.out.println(threeSum.threeSum2(new int[]{0, 0, 0}));
    }

    //要对数组排序双指针
    public List<List<Integer>> threeSum(int[] nums) {
        int length = nums.length;
        if (length < 3) {
            return Collections.emptyList();
        }
        Arrays.sort(nums);
        List<List<Integer>> res = new LinkedList<>();
        int left = 0, right = length - 1;
        while (left + 1 < right) {
            if (nums[left] == 0 && nums[right] == 0) {
                List<Integer> temp = List.of(0, 0, 0);
                res.add(temp);
                break;
            }
            int target = -(nums[left] + nums[right]);
            for (int i = left + 1; i < right; i++) {
                if (nums[i] == target) {
                    List<Integer> temp = List.of(nums[left], nums[i], nums[right]);
                    res.add(temp);
                    break;
                }
            }
            if (target > 0) {
                left++;
            } else if (target < 0) {
                right--;
            } else {
                //等于0过滤重复
                while (right > left + 1 && nums[right] == nums[right - 1]) {
                    right--;
                }
                while (left < right - 1 && nums[left] == nums[left + 1]) {
                    left++;
                }
                //相等的时候不好处理
                //固定要改动的指针
                int temp = -nums[left];
                for (int i = left + 1, j = right - 1; i < j; ) {
                    if (nums[i] + nums[j] > temp) {
                        j--;
                    } else if (nums[i] + nums[j] < temp) {
                        i++;
                    } else {
                        res.add(List.of(nums[left], nums[i], nums[j]));
                        break;
                    }
                }
                left++;
            }
        }
        return res;
    }

    //要对数组排序双指针
    public List<List<Integer>> threeSum2(int[] nums) {
        int length = nums.length;
        if (length < 3) {
            return Collections.emptyList();
        }
        Arrays.sort(nums);
        List<List<Integer>> res = new LinkedList<>();
        for (int i = 0; i < length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {//第一个位置重复的进行计算了
                continue;
            }
            int start = i + 1, end = length - 1;
            while (start < end) {
                int threeSum = nums[i] + nums[start] + nums[end];
                if (threeSum > 0) {
                    end--;
                } else if (threeSum < 0) {
                    start++;
                } else {
                    List<Integer> temp = List.of(nums[i], nums[start], nums[end]);
                    res.add(temp);
                    //相等的时候，要判断下一个节点是否相等，否则就重复了
                    while (start < end && nums[start] == nums[start + 1]) {
                        start++;
                    }
                    while (start < end && nums[end] == nums[end - 1]) {
                        end--;
                    }
                    //相等的时候，左右各减
                    start++;
                    end--;
                }
            }
        }
        return res;
    }
}
